package code1.binary_tree;

/**
 * 原题链接：https://leetcode.cn/problems/convert-bst-to-greater-tree/
 */
public class P538 {

    int curSum=0;           //表示大于当前结点值的和

    //按照右-根-左的顺序遍历
    public int convert(TreeNode root){          //返回大于等于该节点的值的和
        if(root==null){
            return curSum;
        }
        int right=convert(root.right);          //遍历右子树
        root.val+=right;                        //更新根节点的值
        curSum=root.val;
        if(root.left!=null){
            int left = convert(root.left);      //处理左子树,返回值为大于等于左子树值的和
            curSum=left;                        //更新当前和
            return curSum;
        }
        return curSum;
    }

    public TreeNode convertBST(TreeNode root){
        convert(root);
        return root;
    }



}
